|
In graph theory, Berge's lemma states that a matching ''M'' in a graph ''G'' is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with ''M''. It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931). == Proof == To prove Berge's lemma, we first need another lemma. Take a graph ''G'' and let ''M'' and ''M′'' be two matchings in ''G''. Let ''G′'' be the resultant graph from taking the symmetric difference of ''M'' and ''M′''; i.e. (''M'' - ''M′'') ∪ (''M′'' - ''M''). ''G′'' will consist of connected components that are one of the following: # An isolated vertex. # An even cycle whose edges alternate between ''M'' and ''M′''. # A path whose edges alternate between ''M'' and ''M′'', with distinct endpoints. The lemma can be proved by observing that each vertex in ''G′'' can be incident to at most 2 edges: one from ''M'' and one from ''M′''. Graphs where every vertex has degree less than or equal to 2 must consist of either isolated vertices, cycles, and paths. Furthermore, each path and cycle in ''G′'' must alternate between ''M'' and ''M′''. In order for a cycle to do this, it must have an equal number of edges from ''M'' and ''M′'', and therefore be of even length. Let us now prove the contrapositive of Berge's lemma: ''G'' has a matching larger than ''M'' if and only if ''G'' has an augmenting path. Clearly, an augmenting path ''P'' of ''G'' can be used to produce a matching ''M′'' that is larger than ''M'' — just take ''M′'' to be the symmetric difference of ''P'' and ''M'' (''M′'' contains exactly those edges of ''G'' that appear in exactly one of ''P'' and ''M''). Hence, the reverse direction follows. For the forward direction, let ''M′'' be a matching in ''G'' larger than ''M''. Consider ''D'', the symmetric difference of ''M'' and ''M′''. Observe that ''D'' consists of paths and even cycles (as observed by the earlier lemma). Since ''M′'' is larger than ''M'', ''D'' contains a component that has more edges from ''M′'' than ''M''. Such a component is a path in ''G'' that starts and ends with an edge from ''M′'', so it is an augmenting path. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Berge's lemma」の詳細全文を読む スポンサード リンク
|